Searchable symmetric encryption (SSE) enables a client to perform searchesover its outsourced encrypted files while preserving privacy of the files andqueries. Dynamic schemes, where files can be added or removed, leak moreinformation than static schemes. For dynamic schemes, forward privacy requiresthat a newly added file cannot be linked to previous searches. We present a newdynamic SSE scheme that achieves forward privacy by replacing the keys revealedto the server on each search. Our scheme is efficient and parallelizable andoutperforms the best previous schemes providing forward privacy, and achievescompetitive performance with dynamic schemes without forward privacy. Weprovide a full security proof in the random oracle model. In our experiments onthe Wikipedia archive of about four million pages, the server takes one secondto perform a search with 100,000 results.
展开▼